
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <cstdint>
#include <cstddef>
#include <chrono>

#if defined(_MSC_VER)
#include <intrin.h>
#else
#include <x86intrin.h>
#endif //_MSC_VER

#include <emmintrin.h>

#if defined(_MSC_VER)
#include <xatomic.h>
#define __COMPILER_BARRIER() \
    _Compiler_barrier()
#else
#define __COMPILER_BARRIER() \
    __asm volatile ("" : : : "memory")
#endif

alignas(16) std::uint8_t slot[16];

void cpu_warm_up(int delayMillsecs)
{
    using namespace std::chrono;
    double delayTimeLimit = (double)delayMillsecs / 1.0;
    volatile intptr_t sum = 0;

    printf("------------------------------------------\n\n");
    printf("CPU warm-up begin ...\n");

    high_resolution_clock::time_point startTime, endTime;
    duration<double, std::ratio<1, 1000>> elapsedTime;
    startTime = high_resolution_clock::now();
    do {
        for (intptr_t i = 0; i < 500; ++i) {
            sum += i;
            for (intptr_t j = 5000; j >= 0; --j) {
                sum -= j;
            }
        }
        endTime = high_resolution_clock::now();
        elapsedTime = endTime - startTime;
    } while (elapsedTime.count() < delayTimeLimit);

    printf("sum = %d, time: %0.3f ms\n", (int)sum, elapsedTime.count());
    printf("CPU warm-up end   ... \n\n");
    printf("------------------------------------------\n\n");
}

struct ListNode
{
    size_t val{0};
    ListNode *next{nullptr};
    ListNode(size_t x) : val(x) {}
    ListNode() = default;
};

static constexpr std::uint8_t kHashMask     = 0b01111111;
static constexpr std::uint8_t kEmptySlot    = 0b00000000 & kHashMask;
static constexpr std::uint8_t kOverflowMask = 0b10000000;

__m128i _mm_setones_si128()
{
    __m128i ones {};
    ones = _mm_cmpeq_epi16(ones, ones);
    return ones;
}

__m128i _load_data() {
    return _mm_load_si128(reinterpret_cast<const __m128i *>(slot));
}

int match_empty_mask() {
    // Latency = 6
    __m128i ctrl_bits = _load_data();
    __COMPILER_BARRIER();
    __m128i mask_bits = _mm_set1_epi8(kHashMask);
    __COMPILER_BARRIER();

    __m128i empty_bits;
    if (kEmptySlot == 0b00000000)
        empty_bits = _mm_setzero_si128();
    else if (kEmptySlot == 0b11111111)
        empty_bits = _mm_setones_si128();
    else
        empty_bits = _mm_set1_epi8(kEmptySlot);
    
    __m128i match_mask = _mm_cmpeq_epi8(_mm_and_si128(ctrl_bits, mask_bits), empty_bits);
    int mask = _mm_movemask_epi8(match_mask);
    return mask;
}

inline int repeated_hash8(std::uint8_t hash) {
    std::uint32_t hash32 = std::uint32_t(hash) * 0x01010101u;
    return hash32;
}

inline std::uint32_t match_hash(std::uint8_t hash) {
    // Latency = 6
    __m128i ctrl_bits  = _load_data();
    //__COMPILER_BARRIER();
    __m128i mask_bits  = _mm_set1_epi8(kHashMask);
    //__COMPILER_BARRIER();
#if 1
    // Use lookup table
    __m128i hash_bits  = _mm_set1_epi32(repeated_hash8(hash));
#elif 1
    __m128i hash_bits  = _mm_set1_epi64x(hash);
#else
    __m128i hash_bits  = _mm_set1_epi8(hash);
#endif
    __m128i match_mask = _mm_cmpeq_epi8(_mm_and_si128(ctrl_bits, mask_bits), hash_bits);
    int mask = _mm_movemask_epi8(match_mask);
    return static_cast<std::uint32_t>(mask);
}

int main(int argc, char * argv[])
{
    using namespace std::chrono;

    static constexpr intptr_t kMaxCount = 5000000;

    cpu_warm_up(1000);

    ListNode * head = nullptr;
    for (intptr_t i = kMaxCount - 1; i >= 0; --i) {
        ListNode * cur = new ListNode(i);
        cur->next = head;
        head = cur;
    }

    if (1) {
        auto begin = high_resolution_clock::now();
        ListNode * cur = head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        auto end = high_resolution_clock::now();

        duration<double> elapsed = duration_cast<duration<double>>(end - begin);
        printf("cur = %p, time1: %0.3f ms\n", cur, elapsed.count() * 1000);
    }

    if (1) {
        auto begin = high_resolution_clock::now();
        ListNode * cur = head;
        while (cur->next != nullptr && cur->next->val != kMaxCount) {
            cur = cur->next;
        }
        auto end = high_resolution_clock::now();

        duration<double> elapsed = duration_cast<duration<double>>(end - begin);
        printf("cur = %p, time2: %0.3f ms\n", cur, elapsed.count() * 1000);
    }

    if (1) {
        auto begin = high_resolution_clock::now();
        ListNode * cur = head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        auto end = high_resolution_clock::now();

        duration<double> elapsed = duration_cast<duration<double>>(end - begin);
        printf("cur = %p, time3: %0.3f ms\n", cur, elapsed.count() * 1000);
    }

    if (1) {
        auto begin = high_resolution_clock::now();
        ListNode * cur = head;
        while (cur->next != nullptr && cur->next->val != kMaxCount) {
            cur = cur->next;
        }
        auto end = high_resolution_clock::now();

        duration<double> elapsed = duration_cast<duration<double>>(end - begin);
        printf("cur = %p, time4: %0.3f ms\n", cur, elapsed.count() * 1000);
    }

    int empty_mask = match_empty_mask();
    printf("empty_mask = %d\n", empty_mask);

    int ctrl_hash = (int)(size_t)(&empty_mask) & 0x7F;
    int match_mask = match_hash(ctrl_hash);
    printf("match_mask = %d\n", match_mask);

    printf("\n");
    return 0;
}
